package cn.edu.zufe.mjt.manualhashmap;

/**
 * @author 蒙锦涛
 * @date 2025/5/13
 * @description 实现一个简单的HashMap
 */

public class MyHashMap<K, V> {

    @SuppressWarnings("unchecked")
    Node<K, V>[] table = new Node[16];
    private int size = 0;
    // 先用ArrayList代替数组，本质上就是动态数组，先不用考虑扩容问题
//    List<Node<K, V>> table = new ArrayList<>();

    /**
     * @param key map中的key
     * @param value map中的value
     * @return map中key对应的value
     */
    public V put(K key, V value) {
        int keyIndex = indexOf(key);
        Node<K, V> head = table[keyIndex];
        if (head == null) {
            table[keyIndex] = new Node<>(key, value);
            size++;
            resizeIfNecessary();
            return null;
        }
        while (true) {
            if (head.key.equals(key)) {
                V oldValue = head.value;
                head.value = value;
                return oldValue;
            }
            if (head.next == null) {
                head.next = new Node<>(key, value);
                size++;
                resizeIfNecessary();
                return null;
            }
            head = head.next;
        }
    }

    public V get(K key) {
        int keyIndex = indexOf(key);
        Node<K, V> head = table[keyIndex];
        while (head != null) {
            if (head.key.equals(key)) {
                return head.value;
            }
            head = head.next;
        }
        return null;
    }

    public V remove(K key) {
         /*
         [1,2,3,null,null]  length=5; size = 3
         [1,2,3,4,null]  length=5; size = 4
         动态数组的移动，后续手写ArrayList会提，这里简单说明数组的删除，只需要将size减一，后面的元素是否置为null都不会影响遍历
         */
        int keyIndex = indexOf(key);
        Node<K, V> head = table[keyIndex];
        if (head == null) {
            return null;
        }
        if (head.key.equals(key)) {
            table[keyIndex] = head.next;
            size--;
            return head.value;
        }
        Node<K, V> prev = head;
        Node<K, V> current = head.next;
        while (current != null) {
            if (current.key.equals(key)) {
                prev.next = current.next;
                return current.value;
            }
            prev = prev.next;
            current = current.next;
        }
        return null;
    }

    public void resizeIfNecessary() {
        if (size < table.length * 0.75) {
            return;
        }
        @SuppressWarnings("unchecked")
        Node<K, V>[] newTable = new Node[table.length * 2];
        for (Node<K, V> head : table) {
            if (head == null) {
                continue;
            }
            Node<K, V> current = head;
            // 经典的头插法，存在循环链表的情况
            while (current != null) {
                int newIndex = current.key.hashCode() & (newTable.length - 1);
	            Node<K, V> next = current.next;
	            if (newTable[newIndex] == null) {
		            newTable[newIndex] = current;
                    current.next = null;
	            } else {
		            current.next = newTable[newIndex];
                    newTable[newIndex] = current;
	            }
	            current = next;
            }
        }
        this.table = newTable;
        System.out.println("扩容到" + this.table.length);
    }

    public int size() {
        return size;
    }

    private int indexOf(Object key) {
        return key.hashCode() & (table.length - 1);
    }

    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }















}
